package org.blogwu.learn.algorithm.树.二叉搜索树;

import org.blogwu.learn.algorithm.树.二叉搜索树.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.concurrent.ConcurrentLinkedQueue;

public class BinarySearchTree<E> implements BinaryTreeInfo {


    /**
     * 外部自定义比较方式
     *
     * @author hyf
     * @date 2019-07-09
     **/
    private Comparator<E> comparable;

    private int size;

    /**
     * 二叉树根节点
     */
    private Node<E> root;

    /**
     * 元素数量
     *
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     * 是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return this.size < 1;
    }

    /**
     * 清空所有元素
     */
    public void clear() {

    }

    /**
     * 添加元素
     *
     * @param element
     */
    public void add(E element) {
        elementNotNull(element);
        // 初始化根节点
        if (root == null) {
            root = new Node<E>(element);
            size++;
            return;
        }
        // 非第一个节点
        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;
        // 一直遍历
        while (node != null) {
            cmp = this.compare(element, node.element);
            // 保存父节点
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {  // 相等
                node.element = element;
                return;
            }
        }
        // 插入节点
        Node<E> newNode = new Node<E>(element, parent);
        // 保存父节点
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
    }

    /**
     * 删除元素, 此处不使用parent是为了 兼容 leetcode 450题。
     *
     * @param element
     */
    public void remove(E element) {
        this.remove(findNode(this.root, element));
    }

    public void remove(Node<E> node) {
        if (node == null) return;
        size--;
        // 度为2
        if (node.left != null && node.right != null) {
            // 找到后继节点
            Node<E> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值。
            node.element = s.element;
            // 删除后继节点，后续直接删除node就行了
            node = s;
        }
        Node<E> replacement = node.left != null ? node.left : node.right;
        // 那么就是度为1的
        if (replacement != null) {
            // 更改parent
            replacement.parent = node.parent;
            if (node.parent != null) {
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else if (node == node.parent.right) {
                node.parent.right = replacement;
            }

        } else if (node.parent == null) {
            // node是 叶子节点且是根节点。
            root = null;
        } else {
            // 叶子节点
            if (node == node.parent.right) {
                node.parent.right = null;
            } else {
                node.parent.left = null;
            }
        }
    }

    private Node<E> findNode(Node<E> node, E val) {
        while (node != null) {
            int cmp = this.compare(val, node.element);
            if (cmp == 0) {
                return node;
            } else if (cmp > 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    private Node<E> successor(Node<E> node) {
        Node<E> temp = node.right;
        while (temp.left != null) {
            temp = temp.left;
        }
        return temp;
    }

    public void removeOld(Node<E> root, E key) {
        if (root == null) return;
        // 先找到改节点
        Node<E> parent = null;

        Node<E> node = root;
        while (node != null) {
            int cmp = this.compare(key, node.element);
            if (cmp == 0) {
                break;
            } else if (cmp > 0) {
                // 如果为null了，肯定是没找到
                parent = node;
                node = node.right;
            } else if (cmp < 0) {
                parent = node;
                node = node.left;
            }
        }
        if (node == null) return;

        Node<E> frontNode = node.left;
        Node<E> frontNodeParent = node;
        // 寻找前驱节点
        while (frontNode != null) {
            if (frontNode.right != null) {
                System.out.println("xxxxx:" + frontNode.right);
                frontNodeParent = frontNode;
            }
            if (frontNode.right == null) {
                System.out.println("-----:" + frontNode);
                break;
            }
            frontNode = frontNode.right;
        }

        // 判断是否是 叶子节点
        if (node.left == null && node.right == null) {
            if (parent == null) {
                node = null;
                root = null;
            } else {
                if (parent.left == node) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }
            node = null;
            return;
        }
        // 非叶子节点 度数为2的节点  前驱替换当前
        System.out.println("frontNode:" + frontNode);
        if (node.left != null && node.right != null) {
            node.element = frontNode.element;
            if (parent != null) {
                node.left = frontNode.left;
                System.out.println("111:");

            }
            if (frontNodeParent.left == frontNode) {
                System.out.println("---");
                frontNodeParent.left = frontNode.left;
            }
            if (frontNodeParent.right == frontNode) {
                frontNodeParent.right = frontNode.right;
            }
            frontNode = null;
            return;
        }


        // 剩下情况就是度数为1的节点
        if (node.left != null || node.right != null) {
            if (node.left != null) {
                node.element = node.left.element;
                node.left = null;
            } else {
                node.element = node.right.element;
                node.right = null;
            }
//            if ( parent == null){
//            }else{
//                if ( parent.left == node ){
//                    parent.left = null;
//                }else{
//                    parent.right = null;
//                }
//            }
//            node = null;
        }

    }

    /**
     * 迭代的方式前序遍历
     *
     * @param
     * @return void
     * @author hyf
     * @date 2019-07-11
     */
    public void inorderTraversal() {
        Node<E> temp = root;
        if (temp == null) {
            return;
        }

    }

    /**
     * 二叉树数据不能为空
     * 校验参数是否为空
     *
     * @param element
     */
    private void elementNotNull(E element) {
        if (element == null) throw new IllegalArgumentException("参数不能为空");
    }



    /**
     * 是否包含某元素
     *
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return false;
    }

    /**
     * @return 返回值等于0代表 e1和e2 相等，返回值大于0，代表e1 > e2.
     */
    private int compare(E e1, E e2) {
        // 如果有自定义的比较
        if (this.comparable != null) return this.comparable.compare(e1, e2);

        return ((Comparable) e1).compareTo((Comparable) e2);
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
//        Node<E> myNode = (Node<E>) node;
//        String parentString = "null";
//        if (myNode.parent != null) {
//            parentString = myNode.parent.element.toString();
//        }
//        return myNode.element + "_p(" + parentString + ")";
        return ((Node<E>) node).element;
    }

    private static class Node<E> {
        E element;
        // 左节点
        Node<E> left;
        // 右节点
        Node<E> right;
        // 父节点
        Node<E> parent;

        public Node(E element) {
            this.element = element;
        }

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    '}';
        }

        public Node() {
        }

        public E getElement() {
            return element;
        }

        public void setElement(E element) {
            this.element = element;
        }

        public Node<E> getLeft() {
            return left;
        }

        public void setLeft(Node<E> left) {
            this.left = left;
        }

        public Node<E> getRight() {
            return right;
        }

        public void setRight(Node<E> right) {
            this.right = right;
        }

        public Node<E> getParent() {
            return parent;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }
    }


    public BinarySearchTree(Comparator<E> comparable) {
        this.comparable = comparable;
    }

    public BinarySearchTree() {
    }

    public Node<E> getRoot() {
        return root;
    }


    /**
     * 前序遍历e
     * 前序遍历，先打印当前节点。在遍历左叶子节点，左叶子节点遍历在遍历右叶子节点。
     *
     * @param node nood节点
     * @return void
     * @author hyf
     * @date 2019-07-10
     */
    public static void preorderTraversal(Node node) {
        System.out.println(node.element);
        if (node.left != null) {
            preorderTraversal(node.left);
        }
        if (node.right != null) {
            preorderTraversal(node.right);
        }
    }

    /**
     * 中序遍历e
     * 先遍历左叶子节点，在打印当前节点，遍历右叶子节点。在去打印父级
     * 最终的结果是从小到大打印
     *
     * @param node nood节点
     * @return void
     * @author hyf
     * @date 2019-07-10
     */
    public static void inorderTraversal(Node node) {
        if (node.left != null) {
            inorderTraversal(node.left);
        }
        System.out.println(node.element);
        if (node.right != null) {
            inorderTraversal(node.right);
        }

//        if (node.right != null) {
//            inorderTraversal(node.right);
//        }
//        System.out.println(node.element);
//        if (node.left != null) {
//            inorderTraversal(node.left);
//        }

        // 迭代方式
//        Stack<Node<E>> s = new Stack<Node<E>>();
//        do {
//            // 1. 首先吧全部 左节点放进去
//            //
//            while (temp != null) {
//                s.push(temp);
//                temp = temp.left;
//            }
//            if (!s.isEmpty()) {
//                Node node = s.pop();
//                System.out.println(node.element+",");
//                temp = node.right;
//            }
//        } while (!s.isEmpty() || temp != null);

    }

    /**
     * 后序遍历
     * 先遍历左子树、后遍历右子树、根节点。
     *
     * @param node nood节点
     * @return void
     * @author hyf
     * @date 2019-07-10
     */
    public static void postorderTraversal(Node node) {
        if (node.left != null) {
            postorderTraversal(node.left);
        }
        if (node.right != null) {
            postorderTraversal(node.right);
        }
        System.out.println(node.element);
    }

    /**
     * 层序遍历
     * 从root开始，一层一层遍历 ,使用队列来做，当遍历一个节点。吧左节点和右节点 放入队列。然后遍历下一个节点时，从队列中取出下一个节点。
     *
     * @param node nood节点
     * @return void
     * @author hyf
     * @date 2019-07-10
     */
    public static void levelOrderTraversal(Node node) {
        ConcurrentLinkedQueue<Node> queue = new ConcurrentLinkedQueue<>();
        if (node.parent == null) {
            queue.offer(node);
        }
        while (true) {
            Node temp = queue.poll();
            if (temp == null) {
                return;
            }
            System.out.println(temp.element);
            if (temp.left != null) queue.offer(temp.left);
            if (temp.right != null) queue.offer(temp.right);
        }
    }

    /**
     * 层序遍历
     * 从root开始，一层一层遍历 ,使用队列来做，当遍历一个节点。吧左节点和右节点 放入队列。然后遍历下一个节点时，从队列中取出下一个节点。
     *
     * @author hyf
     * @date 2019-07-10
     */
    public void thislevelOrderTraversal(Visitor visitor) {
        ConcurrentLinkedQueue<Node> queue = new ConcurrentLinkedQueue<>();
        queue.offer(this.root);
        int height = 0;
        while (true) {
            Node temp = queue.poll();
            if (temp == null) {
                return;
            }
            visitor.visit(temp.element);
            if (temp.left != null) queue.offer(temp.left);
            if (temp.right != null) queue.offer(temp.right);
        }
    }

    /**
     * 递归 方式求树的高度
     * 思路是：递归迭代所有，然后比对左右两边
     *
     * @author hyf
     * @date 2019-07-10
     */
    public static int heightByRecursive(Node node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(heightByRecursive(node.left), heightByRecursive(node.right));
    }

    /**
     * 层序遍历方式求树的高度
     *
     * @author hyf
     * @date 2019-07-10
     */
    public int heightByIteration(Node root) {
        ConcurrentLinkedQueue<Node> queue = new ConcurrentLinkedQueue<>();
        queue.offer(root);
        int height = 0;
        int currentSize = 1;
        int nextSize = 0;
        while (true) {
            Node temp = queue.poll();
            currentSize--;
            if (temp == null) {
                return height;
            }
            if (currentSize == 0) {
                height++;
            }
            if (temp.left != null) {
                queue.offer(temp.left);
//                nextSize ++;
            }
            if (temp.right != null) {
                queue.offer(temp.right);
//                nextSize ++;
            }
            if (currentSize == 0) {
//                currentSize = nextSize;
////                nextSize = 0;
                currentSize = queue.size();
            }
        }
    }

    /**
     * 判断是不是完全二叉树
     *
     * @author hyf
     * @date 2019-07-10
     */
    public boolean isComplete(Node root) {
        if (root == null) return false;
        ConcurrentLinkedQueue<Node> queue = new ConcurrentLinkedQueue<>();
        queue.offer(root);
        int currentSize = 1;
        boolean upperLevel = true;
        boolean cccx = false;
        boolean xxx = false;
        while (true) {
            boolean xcxczxc = false;
            Node temp = queue.poll();
            currentSize--;
            if (temp == null) {
                return true;
            }
            if ((temp.left != null && temp.right != null)) {
                if (!upperLevel || xxx) {
                    return false;
                }
                queue.offer(temp.left);
                queue.offer(temp.right);
            }
            if ((temp.left == null && temp.right != null)) {
                return false;
            }
            if ((temp.left != null && temp.right == null)) {
                if (!upperLevel || xxx) {
                    return false;
                }
                if (cccx) {
                    xcxczxc = true;
                } else {
                    cccx = true;
                }
                queue.offer(temp.left);
            }
            // 如果这个层级 出现了  双空情况，那么 接下来不能有节点
            if ((temp.left == null && temp.right == null)) {
                upperLevel = false;
                xxx = true;
            }
            if (cccx) {
                upperLevel = false;
            }

            if (currentSize == 0) {
                cccx = false;
                xxx = false;
                currentSize = queue.size();
            }
            if (cccx && xcxczxc) {
                return false;
            }

        }
    }

    /**
     * 判断是不是完全二叉树
     *
     * @author hyf
     * @date 2019-07-10
     */
    public boolean isComplete2(Node root) {
        if (root == null) return false;
        ConcurrentLinkedQueue<Node> queue = new ConcurrentLinkedQueue<>();
        queue.offer(root);
        boolean 叶枝节点 = false;
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (叶枝节点 && !(root.left == null && root.right == null)) {
                return false;
            }

            if (root.left != null && root.right != null) {
                queue.offer(root.left);
                queue.offer(root.right);
            }
            // 此判断可以不要，因为出现  左不为空，有为空的情况，后续都不能出现非叶纸节点。
//            else if ( root.left != null && root.right == null ){
//                queue.offer( root.left );
//                叶枝节点 = true;
//            }
            else if (root.left == null && root.right != null) {
                return false;
            } else {
                叶枝节点 = true;
                if (root.left != null) {
                    queue.offer(root.left);
                }
            }

        }
        return true;
    }

}
